//
// Created by wangwanlong on 2024/6/18.
//

#ifndef MCGPP_GRAPH_PRUNER_H
#define MCGPP_GRAPH_PRUNER_H

#include <algorithm>
#include "config.h"
#include "graph.h"
#include "coarsening_memento.h"
#include "fast_reset_flag_array.h"
//负责维护单点边和平行边的删除和回复
namespace mcgpp {
  //记录每条超边的指纹，即hash值
  struct Fingerprint {
    IDType id; // eid
    int64_t hash;
  };

  struct ParallelE {
    const IDType rep_id; //合并后的住边
    const IDType rmv_id;//被合并的边
  };

  class GraphPruner {
    static constexpr IDType kInvalidID = -1;

  public:
    GraphPruner(const IDType max_num_nodes) :
            _contained_nodes(max_num_nodes) {}

    //移除单点边size = 1
    void removeSingleNodeEdges(ds::GenericGraph &graph, CoarseningMemento &memento) {
      memento.one_pin_es_begin = _removed_single_node_edges.size();
      IDType u = memento.contraction_memento.u;
      auto begin_it = graph.node(u).incidentNets().begin();
      auto end_it = graph.node(u).incidentNets().end();
      for (auto iter = begin_it; iter != end_it; ++iter) {
        if (graph.edge(*iter).size() == 1) {
          //移除，放到末尾
          ++memento.one_pin_es_size;
          _removed_single_node_edges.emplace_back(*iter);
          graph.removeEdge(u, *iter);
          --end_it;
          --iter;
          break;//只有一条单点边
        }
      }
    }

    //合并两条平行边
    void removeParallelEdges(ds::GenericGraph &graph, CoarseningMemento &memento) {
      memento.parallel_es_begin = _removed_parallel_edges.size();
      //创建指纹
      _fingerprints.clear();
      for (IDType e: graph.node(memento.contraction_memento.u).incidentNets())
        _fingerprints.emplace_back(Fingerprint{e, graph.edgeHash(e)});
      std::sort(_fingerprints.begin(), _fingerprints.end(),
                [](const Fingerprint &a, const Fingerprint &b) { return a.hash < b.hash; });
      int i = 0;
      bool filled_probe_bitset = false;
      while (i < _fingerprints.size()) {
        //说明这条边以及被匹配过了
        if (_fingerprints[i].id != kInvalidID) {

          int j = i + 1;
          while (j < _fingerprints.size() && _fingerprints[j].hash == _fingerprints[i].hash) {
            if (_fingerprints[j].id != kInvalidID && graph.edgeSize(_fingerprints[j].id) ==
                                                     graph.edgeSize(_fingerprints[i].id)) {
              if (!filled_probe_bitset) {
                //遍历i的节点
                fillProbeBitset(graph, _fingerprints[i].id);
                filled_probe_bitset = true;
              }

              if (isParallelEdge(graph, _fingerprints[j].id)) {
                //移除平行边
                graph.edge(_fingerprints[i].id).setWeight(graph.edge(_fingerprints[i].id).weight() +
                                                          graph.edge(_fingerprints[j].id).weight());
                graph.removeEdge(_fingerprints[j].id);

                ++memento.parallel_es_size;
                _removed_parallel_edges.emplace_back(ParallelE{_fingerprints[i].id, _fingerprints[j].id});
                _fingerprints[j].id = kInvalidID;//标记匹配
              }
            }
            ++j;
          }
        }
        ++i;
        filled_probe_bitset = false;
      }
    }

    //回复平行边
    void restoreParallelEdges(ds::GenericGraph &graph, const CoarseningMemento &memento) {
      for (int i = memento.parallel_es_begin + memento.parallel_es_size - 1;
           i >= memento.parallel_es_begin; --i) {
//        IDType e = _removed_parallel_edges[i];_removed_parallel_edges[i
        graph.restoreEdge(_removed_parallel_edges[i].rmv_id, _removed_parallel_edges[i].rep_id);

        graph.edge(_removed_parallel_edges[i].rep_id).setWeight(graph.edge(_removed_parallel_edges[i].rep_id).weight() -
                                                                graph.edge(_removed_parallel_edges[i].rmv_id).weight());
        _removed_parallel_edges.pop_back();
      }
    }

    //恢复单点边
    void restoreSingleEdges(ds::GenericGraph &graph, const CoarseningMemento &memento) {
      for (int i = memento.one_pin_es_begin + memento.one_pin_es_size - 1;
           i >= memento.one_pin_es_begin; --i) {

        graph.restoreEdge(_removed_single_node_edges[i]);
        _removed_single_node_edges.pop_back();

      }
    }

    void fillProbeBitset(ds::GenericGraph &graph, const IDType e) {
      _contained_nodes.reset();
      auto begin = graph.edge(e).firstEntry();
      auto end = graph.edge(e).firstInvalidEntry();
      for (auto it = begin; it != end; ++it)
        _contained_nodes.set(graph._incidence_array[it], true);

    }


    bool isParallelEdge(ds::GenericGraph &graph, const IDType e) {
      auto begin = graph.edge(e).firstEntry();
      auto end = graph.edge(e).firstInvalidEntry();
      for (auto it = begin; it != end; ++it) {
        if (!_contained_nodes[graph._incidence_array[it]])
          return false;
      }
      return true;
    }

    std::vector<IDType> _removed_single_node_edges;//保存所有被移除的单点边

    //删除平行边相关数据结构
    std::vector<Fingerprint> _fingerprints;//边的
    std::vector<ParallelE> _removed_parallel_edges;//保存所有被移除的平行边
    ds::FastResetFlagArray<uint64_t> _contained_nodes;

  };
}
#endif //MCGPP_GRAPH_PRUNER_H
